package com.example.hot100;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 *
 *  示例 1：
 * 输入：matrix = [['1','0','1','0','0'],['1','0','1','1','1'],['1','1','1','1','1'],['1','0','0','1','0']]
 * 输出：6
 * 解释：最大矩形如上图所示。
 *
 *  示例 2：
 * 输入：matrix = []
 * 输出：0
 *
 *  示例 3：
 * 输入：matrix = [['0']]
 * 输出：0
 */
public class Leetcode85_MaximalRectangle {
    public static void main(String[] args) {
        char[][] matrix = {
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}};
//        matrix = new char[0][0];

        System.out.println(new Solution().maximalRectangle(matrix));
    }

    static class Solution {
        /**
         * 该问题可以转化成 84 柱状图中最大的矩形
         * 将二维矩阵的每列中 '1' 的总高度看成该层列的高度，即可将该问题转化成逐层求 84 的问题
         * @param matrix
         * @return
         */
        public int maximalRectangle2(char[][] matrix) {
            int rows = matrix.length;
            if (rows == 0) return 0;
            int columns = matrix[0].length;
            if (columns == 0) return 0;
            int res = 0;
            int[] heights = new int[columns];

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (matrix[i][j] == '1') heights[j] += 1;
                    else heights[j] = 0;
                }

                // 每计算完一层的heights 就要计算一次该层的最大矩形面积
                res = Math.max(res, largestRectangleArea(heights));
            }

            return res;
        }

        // 同 84 解法一样使用单调栈进行优化
        private int largestRectangleArea(int[] heights) {
            if (heights == null || heights.length == 0) return 0;
            if (heights.length == 1) return heights[0];

            int len = heights.length;
            int[] left = new int[len];// left[i]表示 heights[i] 的左边界
            int[] right = new int[len];// right[i]表示 heights[i] 的右边界

            Deque<Integer> stack = new LinkedList<>();
            for (int i = 0; i < len; i++) {
                while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i])// 先把所有高度大于等于 height[i] 的值全部移除
                    stack.pollLast();

                left[i] = stack.isEmpty() ? -1 : stack.peekLast();// 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的左边界为 -1(哨兵)
                stack.addLast(i); // i 压入 stack 中，开始下一轮的枚举
            }

            stack.clear(); // 清空栈，为计算所有的右边界做准备

            for (int i = len - 1; i >= 0; i--) {
                while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i])
                    stack.pollLast();
                right[i] = stack.isEmpty() ? len : stack.peekLast();// 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的右边界为 len(哨兵)
                stack.addLast(i);// i 压入 stack 中，开始下一轮的枚举
            }

            // 计算每个高度对应的矩形面积并更新结果
            int maxArea = 0;
            for (int i = 0; i < len; i++) {
                int area = heights[i] * (right[i] - left[i] - 1);
                maxArea = Math.max(maxArea, area);
            }
            return maxArea;
        }

        /**
         * 基于暴力法的优化解法
         * 暴力法:枚举所有可能的矩形判断该矩形是否是全 '1' 的，如果是则更新(超时)
         *
         * 优化方法:
         * 先计算出每个元素在当前行左边的连续 '1'的个数
         * 然后再再这个的基础上依次遍历可能的高，得到当前元素的最大矩形面积
         *
         *
         * @param matrix
         * @return
         */
        public int maximalRectangle1(char[][] matrix) {
            int rows = matrix.length;
            if (rows == 0) return 0;
            int columns = matrix[0].length;
            if (columns == 0) return 0;
            int res = 0;
            int[][] left = new int[rows][columns]; // left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (matrix[i][j] == '1')
                        left[i][j] = (j == 0 ? 1 : left[i][j - 1] + 1);
                }
            }

            // 计算以 (i, j) 为右下角的最大矩阵
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (matrix[i][j] == '1') {
                        int width = left[i][j], area = width;// 初始化以 (i,j) 为右下角的最大矩形面积(此时高度为1)
                        for (int k = i; k >= 0; k--) {// 依次向上扩展高度，并计算可能的最大矩形面积
                            width = Math.min(left[k][j], width);
                            area = width * (i - k + 1); // (i - k + 1) 为高度
                            res = Math.max(area, res);
                        }
                    }
                }
            }

            return res;
        }

        public int maximalRectangle(char[][] matrix) {
            return maximalRectangle2(matrix);
        }
    }
}
